package com.example.demo.java.container.map;

/**
 * 线程安全的HashMap(只针对自身线程安全)
 */
public class UDConcurrentHashMap {

    /** 1、ConcurrentHashMap 问题梳理 (带着问题去看) */
        // (1) ConcurrentHashMap在1.7和1.8做了哪些改变？(数据结构等)
        // (2) get没有加锁，怎么保证数据是准确的？
        // (3) put流程？
        // (4) 讲一讲扩容过程吧？
        // (5) ConcurrentHashMap 与 HashMap的区别？
        // (6) ConcurrentHashMap JDK1.7与1.8的区别？
        // (7) ConcurrentHashMap 在 JDK 1.8 中，为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？
        // (8) ConcurrentHashMap迭代器是强一致性还是弱一致性？HashMap呢？Fast-Fail

    /**
     * 一、数据结构：
     *      因为 HashMap 并不支持在多线程环境下使用，
     *      JDK1.8 中的 ConcurrentHashMap 和往期 JDK 中的
     *      ConcurrentHashMa 一样支持并发操作，整体结构和 JDK1.8 中的 HashMap 类似，
     *      相比 JDK1.7 中的 ConcurrentHashMap， 它抛弃了原有的 Segment 分段锁实现，
     *      采用了 CAS + synchronized 来保证并发的安全性。
     *
     *      CAS(乐观锁):
     *          对CAS的理解，CAS是一种无锁算法，CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。
     *          当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则返回false。
     *      CAS比较与交换的伪代码可以表示为：
     *      do{
     *          备份旧数据；
     *          基于旧数据构造新数据；
     *      }while(!CAS( 内存地址，备份的旧数据，新数据 ))
     */
              /** JDK1.8 中的 ConcurrentHashMap 对节点Node类中的共享变量，和 JDK1.7 一样，
                    使用volatile关键字，保证多线程操作时，变量的可见行！ */
        //    static class Node<K, V> implements Map.Entry<K, V> {
        //        final int hash;
        //        final K key;
        //        volatile V val;
        //        volatile ConcurrentHashMap.Node<K, V> next;

    /**
     * 二、ConcurrentHashMap源码分析
     */

        /** 1、hash算法 */
                  /** 跟HashMap的hash算法类似，只是把位数控制在int最大整数之内。 */
            //    static final int spread(int h) {
            //        return (h ^ h >>> 16) & 2147483647;
            //    }

        /** 2.基础参数 */
            //默认最大的容量
            private static final int MAXIMUM_CAPACITY = 1 << 30;
            //默认初始化的容量
            private static final int DEFAULT_CAPACITY = 16;
            //最大的数组可能长度
            static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
            //默认的并发级别，目前并没有用，只是为了保持兼容性
            private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
            //和hashMap一样，负载因子
            private static final float LOAD_FACTOR = 0.75f;
            //和HashMap一样，链表转换为红黑树的阈值，默认是8
            static final int TREEIFY_THRESHOLD = 8;
            //红黑树转换链表的阀值，默认是6
            static final int UNTREEIFY_THRESHOLD = 6;
            //进行链表转换最少需要的数组长度，如果没有达到这个数字，只能进行扩容
            static final int MIN_TREEIFY_CAPACITY = 64;
            //table扩容时, 每个线程最少迁移table的槽位个数
            private static final int MIN_TRANSFER_STRIDE = 16;
            //感觉是用来计算偏移量和线程数量的标记
            private static int RESIZE_STAMP_BITS = 16;
            //能够调整的最大线程数量
            private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
            //记录偏移量
            private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
            //值为-1, 当Node.hash为MOVED时, 代表着table正在扩容
            static final int MOVED     = -1;
            //TREEBIN, 置为-2, 代表此元素后接红黑树
            static final int TREEBIN   = -2;
            //感觉是占位符，目前没看出来明显的作用
            static final int RESERVED  = -3;
            //主要用来计算Hash值的
            static final int HASH_BITS = 0x7fffffff;
            //节点数组
            //transient volatile Node<K,V>[] table;
            //table迁移过程临时变量, 在迁移过程中将元素全部迁移到nextTable上
            //private transient volatile Node<K,V>[] nextTable;
            //基础计数器
            private transient volatile long baseCount;
            //table扩容和初始化的标记，不同的值代表不同的含义，默认为0，表示未初始化
            //-1: table正在初始化;小于-1，表示table正在扩容；大于0，表示初始化完成后下次扩容的大小
            private transient volatile int sizeCtl;
            //table容量从n扩到2n时, 是从索引n->1的元素开始迁移, transferIndex代表当前已经迁移的元素下标
            private transient volatile int transferIndex;
            //扩容时候，CAS锁标记
            private transient volatile int cellsBusy;
            //计数器表，大小是2次幂
            //private transient volatile CounterCell[] counterCells;

        /**
         * =========================================3.重要方法分析=========================================
         * (1)、获取数据  get
         * (2)、存储数据  put -> putVal
         * (3)、扩容方法  addCount
         * (4)、删除数据  remove -> removeNode
         */
            /*
                //以volatile读的方式读取table数组中的元素
                    static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
                        return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
                    }
                //以volatile写的方式，将元素插入table数组
                    static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
                        U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
                    }
                //以CAS的方式，将元素插入table数组
                    static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                                        Node<K,V> c, Node<K,V> v) {
                        //原子的执行如下逻辑：如果tab[i]==c,则设置tab[i]=v，并返回ture.否则返回false
                        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
                    }
            */

            /**
             * (1)、获取数据  get
             */
                //    public V get(Object key) {
                //        int h = spread(key.hashCode());
                //        ConcurrentHashMap.Node[] tab;
                //        ConcurrentHashMap.Node e;
                //        int n;
                          /** 第 1 步，判断数组是否为空，通过 key 定位到数组下标是否为空
                              tabAt: 寻找指定数组在内存中i位置的数据 */
                //        if ((tab = this.table) != null && (n = tab.length) > 0 && (e = tabAt(tab, n - 1 & h)) != null) {
                //            int eh;
                //            Object ek;
                              /** 第 2 步，判断 node 节点第一个元素是不是要找到，如果是直接返回 */
                //            if ((eh = e.hash) == h) {
                //                if ((ek = e.key) == key || ek != null && key.equals(ek)) {
                //                    return e.val;
                //                }
                              /** 遇到 hash < 0 可能能有两种情况：
                                  (1) 该节点是TreeBin节点(红黑树代理节点，其hash值固定为：-2);
                                  (2) ConcurrentHashMap正在扩容当中，并且该hash桶已迁移完毕，该位置被放置了ForwardingNode节点;
                                      1、如果是TreeBin节点，调用TreeBin类的find方法，具体是以链表方式遍历还是红黑树方式遍历视情况而定
                                      2、如果正在扩容中，则跳转到扩容后的新数组上去查找，TreeBin和Node节点都有对应的find方法，具体什么节点类型则调用对应节点类型的find方法 */
                //            } else if (eh < 0) {
                //                ConcurrentHashMap.Node p;
                //                return (p = e.find(h, key)) != null ? p.val : null;
                //            }
                              /** 第 4 步，如果是链表结构，循环遍历判断 */
                //            while((e = e.next) != null) {
                //                if (e.hash == h && ((ek = e.key) == key || ek != null && key.equals(ek))) {
                //                    return e.val;
                //                }
                //            }
                //        }
                //
                //        return null;
                //    }

            /**
             *  (2)、存储数据  put -> putVal
             */
                //    public V put(K key, V value) {
                //        return this.putVal(key, value, false);
                //    }
                      /** onlyIfAbsent 为 false 表示， 如果放置的元素已经存在， 就予以替换 */
                //    final V putVal(K key, V value, boolean onlyIfAbsent) {
                //        if (key != null && value != null) {
                              /** 1.首先对key的原始hash值进行扰动，使元素在数组上面的分布更加均匀 */
                //            int hash = spread(key.hashCode());
                //            int binCount = 0;
                //            ConcurrentHashMap.Node[] tab = this.table;
                              /** 2.进入一个for的死循环，遇到扩容的情况时先帮助扩容，然后继续循环，直至扩容完毕后再执行插入元素的操作 */
                //            while(true) {
                //                int n;
                                  /** 3.如果当前ConcurrentHashMap还未初始化则先进行初始化操作 */
                //                while(tab == null || (n = tab.length) == 0) {
                //                    tab = this.initTable();
                //                }
                //                ConcurrentHashMap.Node f;
                //                int i;
                                  /** 4.如果定位到的数组位置为null，则直接使用CAS的方式将元素设置到该位置上 */
                //                if ((f = tabAt(tab, i = n - 1 & hash)) == null) {
                                      /** 5.使用CAS的方式将元素设置到该位置上，如果设置失败，也就是期间该位置被其他线程先一步设置值到了该位置，则会继续循环，使用后面的链表的方式插入元素 */
                //                    if (casTabAt(tab, i, (ConcurrentHashMap.Node)null, new ConcurrentHashMap.Node(hash, key, value))) {
                //                        break;
                //                    }
                //                } else {
                //                    int fh;
                                      /** 6.如果发现定位到的节点的hash值为 -1(MOCED)，说明该集合正处于扩容阶段，并且定位到的该hash桶已迁移完毕，
                                              该则优先帮助扩容集合进行扩容，扩容完毕后再继续循环，直至成功插入元素为止 */
                //                    if ((fh = f.hash) == -1) {
                                          /** 7.进行帮助扩容操作 */
                //                        tab = this.helpTransfer(tab, f);
                //                    } else {
                //                        Object fk;
                //                        Object fv;
                //                        if (onlyIfAbsent && fh == hash && ((fk = f.key) == key || fk != null && key.equals(fk)) && (fv = f.val) != null) {
                //                            return fv;
                //                        }
                //                        V oldVal = null;
                                          /** 8.经过了上面的判断，到达了这里，说明集合不在扩容期间，并且定位到的数组上的hash桶不为空，则先将该数组上的位置的节点锁住 */
                //                        synchronized(f) {
                                              /** 9.这里之所以需要再次判断我们之前锁住的f节点是否和现在i位置上的节点是否相等目的是
                                                      为了防止在加锁的这段时间该位置i上的节点被替换或者删除，从而可能引起的错误 */
                //                            if (tabAt(tab, i) == f) {
                                                  /** 10.fh小于0，为红黑树的TreeBin节点，则以红黑树的方式插入新元素 */
                //                                if (fh < 0) {
                //                                    if (f instanceof ConcurrentHashMap.TreeBin) {
                //                                        binCount = 2;
                //                                        ConcurrentHashMap.TreeNode p;
                                                          /** 11.使用红黑树方式插入新元素，执行putTreeVal方法时，如果发现目标位置为null，则直接插入，
                                                                 如果目标位置已经有值，则仅会返回旧节点，然后根据onlyIfAbsent属性决定是否覆盖链表中该节点的旧value*/
                //                                        if ((p = ((ConcurrentHashMap.TreeBin)f).putTreeVal(hash, key, value)) != null) {
                //                                            oldVal = p.val;
                //                                            if (!onlyIfAbsent) {
                //                                                p.val = value;
                //                                            }
                //                                        }
                //                                    } else if (f instanceof ConcurrentHashMap.ReservationNode) {
                //                                        throw new IllegalStateException("Recursive update");
                //                                    }
                //                                } else {
                                                      /** 12.fh大于等于0说明该节点为普通的Node链表节点 */
                //                                    label124: {
                //                                        binCount = 1;
                //
                //                                        ConcurrentHashMap.Node e;
                //                                        Object ek;
                                                          /** 13.循环链表，找到为空的next，加到链表的最后 */
                //                                        for(e = f; e.hash != hash || (ek = e.key) != key && (ek == null || !key.equals(ek)); ++binCount) {
                //                                            ConcurrentHashMap.Node<K, V> pred = e;
                //                                            if ((e = e.next) == null) {
                //                                                pred.next = new ConcurrentHashMap.Node(hash, key, value);
                //                                                break label124;
                //                                            }
                //                                        }
                //
                //                                        oldVal = e.val;
                //                                        if (!onlyIfAbsent) {
                //                                            e.val = value;
                //                                        }
                //                                    }
                //                                }
                //                            }
                //                        }
                                          /** 14.这里面的binCount属性的值是上面的普通Node链表的长度 */
                //                        if (binCount != 0) {
                                              /** 15.如果链表长度大于或者等于TREEIFY_THRESHOLD(这里是8)，调用treeifyBin方法尝试将其转化为红黑树 */
                //                            if (binCount >= 8) {
                                                  /** 16.treeifyBin的操作是，判断当前数组长度是否小于64，如果小于64则会进行扩容，而不会转化为红黑树，
                                                         只有数组长度大于或等于64时遇到链表长度达到8时才会将链表转化为红黑树 */
                //                                this.treeifyBin(tab, i);
                //                            }
                //
                //                            if (oldVal != null) {
                //                                return oldVal;
                //                            }
                //                            break;
                //                        }
                //                    }
                //                }
                //            }
                              /** 17.最后将集合容量进行加1操作 */
                //            this.addCount(1L, binCount);
                //            return null;
                //        } else {
                //            throw new NullPointerException();
                //        }
                //    }

                    /** 代码块2.1 initTable 初始化数组 */
                        //    private final ConcurrentHashMap.Node<K, V>[] initTable() {
                        //        ConcurrentHashMap.Node[] tab;
                        //        while((tab = this.table) == null || tab.length == 0) {
                        //            int sc;
                                      /** 1.sizeCtl默认是0，用来控制table的初始化和扩容操作，
                                            使用了volatile关键字修饰保证并发的可见性
                                            如过一个线程发现sizeCtl < 0，意味着另外的线程执行CAS操作成功，
                                            当前线程只需要让出cpu时间片 */
                        //            if ((sc = this.sizeCtl) < 0) {
                        //                Thread.yield();
                                      /** 2.通过CAS方法，将sizeCtl修改为-1，有且只有一个线程能够修改成功 */
                        //            } else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
                        //                try {
                                              /** 3.初始化位桶 */
                        //                    if ((tab = this.table) == null || tab.length == 0) {
                        //                        int n = sc > 0 ? sc : 16;
                        //                        ConcurrentHashMap.Node<K, V>[] nt = new ConcurrentHashMap.Node[n];
                        //                        tab = nt;
                        //                        this.table = nt;
                        //                        sc = n - (n >>> 2);
                        //                    }
                        //                    break;
                        //                } finally {
                        //                    this.sizeCtl = sc;
                        //                }
                        //            }
                        //        }
                        //
                        //        return tab;
                        //    }

                    /** 代码块2.2 helpTransfer 帮助扩容 */
                        //    final ConcurrentHashMap.Node<K, V>[] helpTransfer(ConcurrentHashMap.Node<K, V>[] tab, ConcurrentHashMap.Node<K, V> f) {
                        //        ConcurrentHashMap.Node[] nextTab;
                                  /** 1.如过table不为空且node节点是转移类型，同时node节点的nextTable（新table）不为空，进行数据校验 */
                        //        if (tab != null && f instanceof ConcurrentHashMap.ForwardingNode &&
                        //                (nextTab = ((ConcurrentHashMap.ForwardingNode)f).nextTable) != null) {
                                      /** 2.满足以上条件之后，尝试帮助扩容，根据数组的length得到一个标识符号 */
                        //            int rs = resizeStamp(tab.length);
                        //            int sc;
                                      /** 3.如过nextTab没有被并发修改且tab也没有被并发修改，同时sizeCtl < 0， 说明还在扩容
                                            对sizeCtl参数值进行分析判断（此处为反向判断）
                                            判断1：如果sizeCtl无符号右移16不等于rs，说明标识符变化了
                                            判断2：如果sizeCtl == rs + 1，表示扩容结束了，不再有线程进行扩容
                                            判断3：如果sizeCtl == rs + 65535，表示达到最大帮助线程数量，即65535
                                            判断4：如果转移下标transferIndex < 0，表示扩容结束
                                            满足任何一个，结束循环，返回table */
                        //            while(nextTab == this.nextTable && this.table == tab &&
                        //                    (sc = this.sizeCtl) < 0 && sc >>> 16 == rs && sc != rs + 1 &&
                        //                    sc != rs + '\uffff' && this.transferIndex > 0) {
                                          /** 4.如过以上都不是，使用CAS，将sizeCtl + 1，表示增加了一个线程帮助其扩容 */
                        //                if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) {
                                              /** 5.对数组进行转移，执行完之后结束循环 */
                        //                    this.transfer(tab, nextTab);
                        //                    break;
                        //                }
                        //            }
                        //
                        //            return nextTab;
                        //        } else {
                        //            return this.table;
                        //        }
                        //    }

            /**
             * (3)、扩容方法  addCount
             */
                //    private final void addCount(long x, int check) {
                          /** 1.从putVal传入的参数是 x=1、check=0，只有hash冲突且它的结构是链表的结构时，check才会大于1 */
                //        ConcurrentHashMap.CounterCell[] cs;
                //        long b;
                //        long s;
                //        int sc;
                          /** 2.利用CAS方法更新baseCount的值 */
                //        if ((cs = this.counterCells) != null ||
                //        !U.compareAndSetLong(this, BASECOUNT, b = this.baseCount, s = b + x)) {
                //            boolean uncontended = true;
                //            ConcurrentHashMap.CounterCell c;
                //            long v;
                //            if (cs == null || (sc = cs.length - 1) < 0 ||
                //            (c = cs[ThreadLocalRandom.getProbe() & sc]) == null ||
                //            !(uncontended = U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))) {
                //                this.fullAddCount(x, uncontended);
                //                return;
                //            }
                //            if (check <= 1) {
                //                return;
                //            }
                //            s = this.sumCount();
                //        }
                //        int n;
                //        ConcurrentHashMap.Node[] tab;
                          /** 3.检查是否需要扩容，默认check=1，需要检查 */
                //        if (check >= 0) {
                              /** 4.如果map.size()大于等于sizeCtl（达到扩容阈值需要扩容）并且table不为空，
                                    同时table的长度小于最大容量，可以扩容 */
                //            for(; s >= (long)(sc = this.sizeCtl) && (tab = this.table) != null
                //            && (n = tab.length) < 1073741824; s = this.sumCount()) {
                                  /** 5.根据length得到一个标识 */
                //                int rs = resizeStamp(n);
                                  /** 6.sc=sizeCtl，如果小于0，表示正在扩容，尝试帮助扩容 */
                //                if (sc < 0) {
                //                    ConcurrentHashMap.Node[] nt;
                                      /** 7.调用扩容前的判断
                                             判断1：如果sizeCtl无符号右移16不等于rs，说明标识符变化了
                                             判断2：如果sizeCtl == rs + 1，表示扩容结束了，不再有线程进行扩容
                                             判断3：如果sizeCtl == rs + 65535，表示达到最大帮助线程数量，即65535
                                             判断4：如果nextTable为空，表示扩容结束
                                             判断5：如果转移下标transferIndex < 0，表示扩容结束
                                             满足任何一个判断，结束循环，返回table
                                      */
                //                    if (sc >>> 16 != rs || sc == rs + 1 || sc == rs + '\uffff' ||
                //                    (nt = this.nextTable) == null || this.transferIndex <= 0) {
                //                        break;
                //                    }
                                      /** 8.使用CAS更新数量，并调用扩容方法 */
                //                    if (U.compareAndSetInt(this, SIZECTL, sc, sc + 1)) {
                //                        this.transfer(tab, nt);
                //                    }
                                  /** 9.如果不在扩容，将sizeCtl更新：标识符左移16位+2，也就是变成一个负数 */
                //                } else if (U.compareAndSetInt(this, SIZECTL, sc, (rs << 16) + 2)) {
                                      /** 10.进行扩容处理 */
                //                    this.transfer(tab, (ConcurrentHashMap.Node[])null);
                //                }
                //            }
                //        }
                //
                //    }

            /**
             * (4)、删除数据  remove -> removeNode
             */
                //    public V remove(Object key) {
                //        return this.replaceNode(key, (Object)null, (Object)null);
                //    }

                //    final V replaceNode(Object key, V value, Object cv) {
                //        int hash = spread(key.hashCode());
                //        ConcurrentHashMap.Node[] tab = this.table;
                //
                //        ConcurrentHashMap.Node f;
                //        int n;
                //        int i;
                          /** 1.循环存储桶，当前索引位置节点不是空 */
                //        while(tab != null && (n = tab.length) != 0 && (f = tabAt(tab, i = n - 1 & hash)) != null) {
                //            int fh;
                              /** 2.如果发现定位到的节点的hash值为 -1(MOCED)，说明该集合正处于扩容阶段 */
                //            if ((fh = f.hash) == -1) {
                                  /** 3.帮助扩容 */
                //                tab = this.helpTransfer(tab, f);
                //            } else {
                //                V oldVal = null;
                //                boolean validated = false;
                                  /** 4.利用synchronized同步锁，保证并发时元素移除安全 */
                //                synchronized(f) {
                //                    if (tabAt(tab, i) == f) {
                //                        Object pv;
                                          /** 4.1 fh < 0，节点为红黑树（-2），利用红黑二叉树特性进行查找并移除节点，最后调整红黑二叉树结构 */
                //                        if (fh < 0) {
                //                            if (f instanceof ConcurrentHashMap.TreeBin) {
                //                                validated = true;
                //                                ConcurrentHashMap.TreeBin<K, V> t = (ConcurrentHashMap.TreeBin)f;
                //                                ConcurrentHashMap.TreeNode r;
                //                                ConcurrentHashMap.TreeNode p;
                //                                if ((r = t.root) != null && (p = r.findTreeNode(hash, key, (Class)null)) != null) {
                //                                    pv = p.val;
                //                                    if (cv == null || cv == pv || pv != null && cv.equals(pv)) {
                //                                        oldVal = pv;
                //                                        if (value != null) {
                //                                            p.val = value;
                //                                        } else if (t.removeTreeNode(p)) {
                //                                            setTabAt(tab, i, untreeify(t.first));
                //                                        }
                //                                    }
                //                                }
                //                            } else if (f instanceof ConcurrentHashMap.ReservationNode) {
                //                                throw new IllegalStateException("Recursive update");
                //                            }
                //                        } else {
                                              /** 4.2 判断当前冲突节点，是否为链表结构，如果是循环遍历移除 */
                //                            label125: {
                //                                validated = true;
                //                                ConcurrentHashMap.Node<K, V> e = f;
                //                                ConcurrentHashMap.Node pred = null;
                //                                Object ek;
                //                                while(e.hash != hash || (ek = e.key) != key && (ek == null || !key.equals(ek))) {
                //                                    pred = e;
                //                                    if ((e = e.next) == null) {
                //                                        break label125;
                //                                    }
                //                                }
                //                                pv = e.val;
                //                                if (cv == null || cv == pv || pv != null && cv.equals(pv)) {
                //                                    oldVal = pv;
                //                                    if (value != null) {
                //                                        e.val = value;
                //                                    } else if (pred != null) {
                //                                        pred.next = e.next;
                //                                    } else {
                //                                        setTabAt(tab, i, e.next);
                //                                    }
                //                                }
                //                            }
                //                        }
                //                    }
                //                }
                //                if (validated) {
                //                    if (oldVal != null) {
                //                        if (value == null) {
                                              /** 5.因为check = -1。所以不会进行扩容操作，利用CAS操作修改baseCount值 */
                //                            this.addCount(-1L, -1);
                //                        }
                //                        return oldVal;
                //                    }
                //                    break;
                //                }
                //            }
                //        }
                //        return null;
                //    }

}
